package cn.suchan.jianzhi.q14_findtotail;

/**
 * 知识点：链表中第K个结点
 * 题目描述
 * 输入一个链表，输出该链表中倒数第k个结点。
 *
 * @author suchan
 * @date 2019/05/26
 */
public class Solution {

    /**
     * 链表是从最后面那个开始遍历的吗？
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode FindKthToTail(ListNode head, int k) {

        // 计算链表长度
        int count = 0;
        ListNode node = head;
        while (node != null) {
            count++;
            node = node.next;
        }

        if (count == 0) {
            return null;
        }

        // 计算k代表的链表节点索引（从1开始）(链表从最后那个节点开始遍历)
        int index = 0;
        if (k < 0 && count >= Math.abs(k)) {
            // k是负数，且其绝对值在count范围内
            //index = (count - Math.abs(k)) + 1;
            index = Math.abs(k);
        } else if (k > 0 && count >= k) {
            // k是正整数，且在count范围内
            //index = k;
            index = (count - k) + 1;
        }

        if (index == 0) {
            return null;
        }

        // 第一个节点是自己，第二个节点开始才是next
        while (index > 1) {
            head = head.next;
            index--;
        }
        return head;
    }

    public static void main(String[] main) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        Solution solution = new Solution();
        ListNode node = solution.FindKthToTail(node1, -1);
        if (node != null) {
            System.out.println(node.val);
        } else {
            System.out.println("null");
        }
    }
}
